package cn.designpattern;

import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

public class GenericQuickSort {
    private final static ForkJoinPool forkJoinPool = new ForkJoinPool();

    public static<T> void sort(List<T> list) {
        sort(list,0);
    }

    public static<T> void sort(List<T> list, int number) {
        if(list==null || list.size()==0 || list.size()==1){
            return;
        }
        QuickTask<T> quicklyTask = new QuickTask<>(0, list.size() - 1, list);
        if(number != 0){
            quicklyTask.setNumber(number);
        }
        ForkJoinTask<List<T>> submit = forkJoinPool.submit(quicklyTask);
        submit.join();
    }

    public static class QuickTask<T> extends RecursiveTask<List<T>> {
        private final int left;
        private final int right;
        private final List<T> list;

        public QuickTask(int left, int right, List<T> list) {
            this.left = left;
            this.right = right;
            this.list = list;
        }

        private int number = 9;

        public void setNumber(int number) {
            this.number = number;
        }

        @Override
        protected List<T> compute() {
            if (right - left >= number) {
                int i = sortCompare(left, right, list);
                QuickTask<T> one = new QuickTask<>(left, i - 1, list);
                QuickTask<T> two = new QuickTask<>(i + 1, right, list);
                ForkJoinTask<List<T>> fork1 = one.fork();
                ForkJoinTask<List<T>> fork2 = two.fork();
                fork1.join();
                fork2.join();
            }else {
                quickSort(list, left, right);
            }
            return list;
        }

        public void quickSort(List<T> list, int left, int right){
            if(left<right){
                int i = sortCompare(left, right, list);
                quickSort(list, left, i-1);
                quickSort(list, i+1, right);
            }
        }

        public int sortCompare(int low, int high, List<T> list) {
            T t = list.get(low);
            Comparable<T> tmp = (Comparable<T>) t;
            while (low < high) {
                while (low < high && tmp.compareTo(list.get(high)) <= 0) {
                    high--;
                }
                T t1 = list.get(high);
                list.set(low, t1);
                while (low < high && tmp.compareTo(list.get(low)) >= 0) {
                    low++;
                }
                T t2 = list.get(low);
                list.set(high, t2);
            }
            list.set(low, t);
            return low;
        }
    }
}

